/**
 * 描述
 * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
 * <p>
 * 1.此题对比原题有改动
 * 2.题目保证链表中节点的值互不相同
 * 3.该题只会输出返回的链表和结果做对比
 * <p>
 * 数据范围:
 * 0<=链表节点值<=10000
 * 0<=链表长度<=10000
 */
public class JZ18 {


    /**
     * 但链表的删除过程当中需要记录前置链表的引用,不然就会断链
     * 这个算是常规解法了
     * @param head ListNode类
     * @param val  int整型
     * @return ListNode类
     */
    public static ListNode deleteNode(ListNode head, int val) {
        // write code here

        //考虑空链表情况
        if(head==null) return head;

        //考虑删除首节点情况
        if(head.val == val){
            head=head.next;
            return head;
        }

        //考虑删除非首节点情况
        ListNode p = head;
        while(p.next!=null){
            if(p.next.val==val) {
                p.next = p.next.next;
                return head;
            }
            p=p.next;
        }
        return head;
    }

    /**
     * 采用替换的思想:不适用于尾节点.
     *
     * @param head
     * @param val
     * @return
     */
    public static ListNode deleteNodeMethod2(ListNode head,int val){

        //空链表
        if (head==null) return head;

        ListNode p = head;


        while(p!=null){
            //考虑非尾节点--采用替换的思想
            if(p.val==val&&p.next!=null){//当删除的节点不是尾节点时成立
                p.val=p.next.val;
                p.next=p.next.next;
                return head;
            }
            //考虑尾节点
            if(p.next.val==val&&p.next.next==null){
                p.next=null;
            }
            p=p.next;
        }
        return head;
    }

    public static void main(String[] args) {

        ListNode head=null;
        ListNodeTools tools = new ListNodeTools();//链表工具类
        Integer arr[] = new Integer[]{1,2,3,4,5};
        head=tools.InitListNode(head,arr);//初始化链表

        //do something
//        head=JZ18.deleteNode(head,1);

        head=JZ18.deleteNodeMethod2(head,5);

        tools.readFromHead(head);//从头遍历

    }

}



